package SortSummary;

/*
*   基数排序
*       排序规则：
*       时间复杂度：
*       空间复杂度：
*       稳定性：
* */

class RadixSort {
    static void radixSort(int[] nums){
        int[] tempNums = new int[nums.length];//临时数组，存放排序好的结果
        //获取最大值
        int maxVal = nums[0];
        for(int n:nums){
            maxVal = n>maxVal?n:maxVal;
        }

        int loopTimes = 0;//循环次数
        while(maxVal != 0){//有几位就循环几次
            int[] bucket = new int[10];//桶
            maxVal = maxVal/10;
            loopTimes++;
            //求每个数字出现频率
            for(int n:nums){
                int radix = getRadix(n,loopTimes);
                bucket[radix]++;
            }
            //求频率前缀和
            for(int i=1;i<bucket.length;i++){
                bucket[i] = bucket[i]+bucket[i-1];
            }
            for(int i=nums.length-1;i>=0;i--){
                int n = nums[i];
                int radix = getRadix(n,loopTimes);
                tempNums[bucket[radix]-1] = n;
                bucket[radix]--;
            }
            for(int i=0;i<nums.length;i++){
                nums[i] = tempNums[i];
            }
        }
    }

    //获取数的site位置上的数字
    static int getRadix(int num,int site){
        return (num/(int)(Math.pow(10,site-1)))%10;
    }
}
